package nf;

import nf.graph.*;
import nf.utility.*;
import nf.util.*;
import java.util.*;

public class StableGraphFinder implements Iterable<StableGraphFinder.Result>
{
	private EdgeGame game;
	private GraphGenerator gen;
	
	public StableGraphFinder(EdgeGame game, int nodeCount)
	{
		this.game = game;
		this.gen = new GraphGenerator(nodeCount);
	}
	
	public GraphGenerator getGenerator()
	{
		return gen;
	}
	
	public Iterator<Result> iterator()
	{
		return new StabilityIterator();
	}
	
	private class StabilityIterator implements Iterator<Result>
	{
		private Iterator<Graph> iter;
		
		public StabilityIterator()
		{
			iter = gen.iterator();
		}
	
		public boolean hasNext()
		{
			return iter.hasNext();
		}
		
		public Result next()
		{
			Graph g = iter.next();
			if (null == PropertyBag.Access.get(g, "edgeCost"))
				Simulator.setEdgeCost(g, new Rational(0));
			return new Result(g, game.getCostBounds(g));
		}
		
		public void remove()
		{
			iter.remove();
		}
	}
	
	public static class Result
	{
		public Graph graph;
		public List<Rational> bounds;
		public boolean isStable;
		
		Result(Graph graph, List<Rational> bounds)
		{
			this.graph = graph;
			this.bounds = bounds;
			
			this.isStable = bounds.get(0).compareTo(bounds.get(1)) <= 0;
		}
	}
	
	private static class RunResult
	{
		public int stableCount;
		public int unstableCount;
		public double density;
		
		public RunResult()
		{
			this(0, 0, 0.0d);
		}
		
		public RunResult(int stableCount, int unstableCount, double density)
		{
			this.stableCount = stableCount;
			this.unstableCount = unstableCount;
			this.density = density;
		}
	}
	
	private static void printGraph(FormationGame game, Result res)
	{
		Rational lower = res.bounds.get(0);
		Rational upper = res.bounds.get(1);
		
		Simulator.printNetwork(game, res.graph);
		System.out.printf("density = %.2f%n", res.graph.getDensity());
		System.out.printf("%s (%.4f) | %s (%.4f) ==> %s%n",
			lower, lower.doubleValue(),
			upper, upper.doubleValue(),
			(res.isStable ? "stable" : "never stable")
		);
		System.out.println("=======================================");
	}
	
	private static RunResult runNaive(FormationGame game,
		StableGraphFinder finder, boolean quiet, boolean showUnstable)
	{
		RunResult rr = new RunResult();
		double totalDensity = 0.0d;
	
		for (Result res : finder) {
			if (res.isStable) {
				rr.stableCount++;
				totalDensity += res.graph.getDensity();
			} else {
				rr.unstableCount++;
			}
			
			if (!quiet && (res.isStable || showUnstable))
				printGraph(game, res);
		}
		
		rr.density = totalDensity / (double) rr.stableCount;
		return rr;
	}
	
	private static RunResult runDetectIsomorphisms(FormationGame game,
		StableGraphFinder finder, boolean quiet, boolean showUnstable)
	{
		final IsomorphicComparator gc = new IsomorphicComparator();
		GraphGenerator gen = finder.getGenerator();
		
		int size = gen.getNodeCount();
		int possibleEdges = size * (size - 1);
		ArrayList<List<Result>> sortedResults =
			new ArrayList<List<Result>>(possibleEdges + 1);
			
		for (int i = 0; i < possibleEdges + 1; i++) {
			sortedResults.add(new LinkedList<Result>());
		}

		RunResult rr = new RunResult();
		double totalDensity = 0.0d;
		
		long allPossible = (long) Math.pow(2, gen.countPairs());
		long totalCount = 0;
		long distinct = 0;
		for (Result res : finder) {
			boolean found = false;
			List<Result> results =
				sortedResults.get((int) res.graph.edgeCount());
			for (Result oldRes : results) {
				if (gc.compare(oldRes.graph, res.graph) == 0) {
					found = true;
					break;
				}
			}
			
			if (!found) {
				res.graph = res.graph.copy();
				results.add(res);
				distinct++;
			}
			totalCount++;
			
			System.err.printf("\r%d / %d (%.3f%%)", totalCount, allPossible,
				((double) totalCount / (double) allPossible * 100.0));
				
		}
		System.err.println();
		
		for (List<Result> results : sortedResults) {
			for (Result res : results) {
				if (res.isStable) {
					rr.stableCount++;
					totalDensity += res.graph.getDensity();
				} else {
					rr.unstableCount++;
				}
				
				if (!quiet && (res.isStable || showUnstable))
					printGraph(game, res);
			}
		}
		
		System.out.printf("%d of %d graphs were distinct.%n", distinct,
			totalCount);
		
		rr.density = totalDensity / (double) rr.stableCount;
		return rr;
	}
	
	public static void main(String... args)
	{
		ArgumentParser p = new ArgumentParser();
		p.addOption("quiet", "-q", "--quiet").setImplicitValue(true)
			.setDefaultValue(false);
		p.addOption("unstable", "-s", "--stable-only").setImplicitValue(false)
			.setDefaultValue(true);
		p.addOption("detectIsomorphisms", "-I", "--with-isomorphisms")
			.setImplicitValue(false).setDefaultValue(true);
		p.addOption("utility", "-u", "--util-calc").setValueType(String.class)
			.setDefaultValue("simple");
		
		ArgumentParser.Result r;
		boolean quiet;
		boolean detectIsomorphisms;
		boolean showUnstable;
		
		try {
			r = p.parse(args);
			quiet = r.options.get("quiet") == Boolean.TRUE;
			detectIsomorphisms =
				r.options.get("detectIsomorphisms") == Boolean.TRUE;
			showUnstable = r.options.get("unstable") == Boolean.TRUE;
		} catch (ArgumentParseException e) {
			System.err.println("error: " + e.getMessage());
			System.exit(-1);
			return;
		}
	
		FormationGame game = new FormationGame(null,
			Simulator.getUtilityCalculator((String) r.options.get("utility")));
		StableGraphFinder finder =
			new StableGraphFinder(game, Integer.parseInt(r.args[0]));
		
		RunResult rr = (detectIsomorphisms)
			? runDetectIsomorphisms(game, finder, quiet, showUnstable)
			: runNaive(game, finder, quiet, showUnstable);
			
		if (!detectIsomorphisms) {
			System.out.println("WARNING: Isomorphic graphs were not filtered." +
				" Rerun without --with-isomorphisms.");
		}
		
		System.out.printf("Stable graphs: %d; Unstable graphs: %d%n",
			rr.stableCount, rr.unstableCount);
		System.out.printf("Average density of stable graphs: %.04f%n",
			rr.density);
	}
}
